The present preferred embodiment is directed to an apparatus and method for compressing and decompressing data, and more specifically to sequential data compression and decompression at high speed.
Many types of data compression systems exist. One commonly used technique is the Lempel-Ziv algorithm which is described in “Compression of Individual Sequences via Variable Rate Coding” by Lempel and Ziv in IEEE Transactions on Information Theory, September, 1977, pages 530–536.
The Lempel-Ziv compression algorithm is a variable rate coding technique. One of the primary problems with implementations of the Lempel-Ziv compression technique is the difficulty in performing the search operation for previous matching strings at an effective processing speed.
Today the Lempel-Ziv technique is being used in tape drivers, among other places. The primary problem in implementing the algorithm is obtaining high data rates, even when implemented in hardware. One example of prior art is U.S. Pat. No. 5,652,878. This architecture achieves a speed of one byte per clock cycle.
With the increased capabilities of the mechanical parts of tape drivers and the ever increasing demand for bandwidth, single byte compression is no longer adequate. For a given silicon technology it is impossible to increase the clock frequency above a certain limit without violating signal delay constraints, thus effectively limiting the maximum achievable bandwidth of the prior art. Furthermore, there are issues related to power consumption when increasing the clock frequency.
The compression method presented by Craft (U.S. Pat. No. 5,612,878) is inherently a sequential process which does not easily lend itself to parallelization. Making any system capable of compressing several bytes per cycle is a very significant technical challenge. It is very difficult to construct a system to obtain a real increase in bandwidth. Such systems would give a correspondingly longer delay on the critical path, thereby reducing the clock frequency and offsetting the whole advantage of processing several bytes at a time.
FIG. 1 shows an operations order (system critical path) of a prior art Lempel-Ziv data compression engine having the above-described disadvantages, as disclosed in U.S. Pat. No. 5,612,878. At the beginning of the critical path, a central data register 2 is provided which is connected to receive a clock signal 102 and has a distribute output to a comparator 3 which compares values locally. The comparator 3 has a collect output to a calculation unit 4, which calculates control signals centrally. The calculation unit 4 has a distribute output to an execution unit 5 which executes commands locally. Execution unit 5 outputs to a register 6 which stores historic data locally. Register 6 also is connected to receive a clock signal 102.